package com.lfs.dp;

/*
    机器人不同路径
 */
public class UniquePaths62 {
    /*
        题目给的是m*n的矩阵,那我们的dp数组就应该是二维数组

        1、dp数组的含义:
            dp[i][j]:从dp[0][0]到dp[i][j]有多少种不同的路径

        2、递推公式
            因为我们只能向右走,向下走,所以要想到达x
                                ↓
                             →  x(dp[i][j])
            ↓位置: dp[i-1][j]
            →位置: dp[i][j-1]
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            注意这里一定要明白,从上到dp[i][j],还需要走一步;从左到dp[i][j],还需要走一步,但是
            我们求的是路径,不是步数,虽然从dp[i-1][j]到dp[i][j] 或 dp[i][j-1]到dp[i][j]需要再各走一步,但是路径是不变的,在只能再走一步的前提下,双方的路径那就是唯一的
            所以dp[i][j]的路径就是 dp[i-1][j] + dp[i][j-1] = 从dp[0][0]到dp[i-1][j]的路径 + 从dp[0][0]到dp[i][j-1]的路径

         3、初始化
            注意题目,只能每次只能向下或者向右移动一步,那么第一行 或 第一列 的 所有路径都是1(注意是路径,不是步数),因为只能直来直去
             for (int i = 0; i < m; i++)  dp[i][0] = 1; 列

             for (int i = 0; i < n; i++)  dp[0][i] = 1; 行

     */
    public int uniquePaths(int m, int n) {
        //m表示这个二维数组有多少个数组
        //n表示每一个一维数组的元素个数
        int[][] dp = new int[m][n];//初始化m*n的棋盘

        for (int i = 0; i < m; i++) dp[i][0] = 1;//第一列 路径全都是1 列不变行变,列的值变动
        for (int i = 0; i < n; i++) dp[0][i] = 1;//第一列 路径全都是1

        for (int i = 1; i < m; i++) {//位于(0,0),从(1,1)开始行动
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];//返回索引最后一位
    }
}
